package main

import (
	"math"
	"sort"
)

func minDistance(houses []int, target int) int {
	lh := len(houses)
	dpl := lh + 2
	dp := make([][][]int, dpl)
	for i := 0; i < dpl; i++ {
		dp[i] = make([][]int, dpl)
		for j := 0; j < dpl; j++ {
			dp[i][j] = make([]int, dpl)
			for k := 0; k < dpl; k++ {
				dp[i][j][k] = -1
			}
		}
	}
	sort.Ints(houses)
	return fkdp(0, lh-1, target, dp, houses)
}

func fkdp(i, j, k int, dp [][][]int, h []int) int {
	if i >= j {
		return 0
	}
	if dp[i][j][k] != -1 {
		return dp[i][j][k]
	}
	if k == 1 {
		dp[i][j][k] = findMin(h[i : j+1])
		return dp[i][j][k]
	}
	if j-i+1 <= k {
		dp[i][j][k] = 0
		return dp[i][j][k]
	}
	min := math.MaxInt64
	for x := j; x >= i; x-- {
		tmp := fkdp(x, j, 1, dp, h) + fkdp(i, x-1, k-1, dp, h)
		if tmp < min {
			min = tmp
		}
	}
	dp[i][j][k] = min
	return dp[i][j][k]
}

func findMin(h []int) int {
	min := math.MaxInt64
	hl := len(h)
	for i := 0; i < hl; i++ {
		tmp := 0
		for j := 0; j < hl; j++ {
			tmp += abs(h[i] - h[j])
		}
		if tmp < min {
			min = tmp
		}
	}
	return min
}
func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}
